package org.nowcoder.leetcode.BTree;

/**
 * Title  : 236. Lowest Common Ancestor of a Binary Tree
 * Source : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
 * Author : XrazYang
 * Date   : 2023-09-11
 */

public class LeetCode_236 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private TreeNode ans;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //非递归实现
        // ArrayDeque<TreeNode> sta = new ArrayDeque<>();
        // sta.push(root);

        // //先遍历存储所有结点的父结点
        // HashMap<Integer, TreeNode> fathers = new HashMap<>();
        // fathers.put(root.val, null);
        // while (!sta.isEmpty()) {
        //     TreeNode node = sta.pop();
        //     if (node.right != null) {
        //         sta.push(node.right);
        //        fathers.put(node.right.val, node);
        //     }
        //     if (node.left != null) {
        //         sta.push(node.left);
        //         fathers.put(node.left.val, node);
        //     }
        // }
        // //寻找共同的公共祖先
        // TreeNode node = q;
        // while (p != null) {
        //     while (node != null) {
        //         if (p.val == node.val) {
        //             return node;
        //         }
        //         node = fathers.get(node.val);
        //     }
        //     p = fathers.get(p.val);
        //     node = q;
        // }
        // return root;


        //递归实现
        dfs(root, p, q);
        return ans;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }
}
